The present invention relates to an electrical device for self-clocked controlled pseudo random noise (PN) sequence generation.
Pseudo random noise sequences (PN sequences) are used in many cryptographic and communication applications to provide randomly appearing symbols. Typically, cryptographic applications are methods to provide confidentiality of transmitted information through the use of stream ciphers. In communications systems PN sequences may e.g. be used as spreading sequences in spread-spectrum communications systems where they determine the hop sequence and/or the direct spreading sequence.
In general, a receiver of a spread-spectrum communications system will receive a digital signal/bit stream transmitted over a single carrier frequency which is combined from a digital signal/bit stream containing information such as a digitized voice and from a PN sequence used to code or encrypt the transmission. Typically, the length of the PN sequence stream is much larger than the length of the information stream.
The PN sequences are sometimes derived by using a maximal length polynomial. Constructions, whether hardware or software implemented, which form PN sequences in this manner are sometimes referred to as m-sequence generators. It is well known that the randomness properties of the sequences generated by the m-sequence generators are very limited as a result of linear relationships between the symbols of the sequence. This enables a prediction of the next symbol given sufficiently many, but small number of previous symbols. In various applications this is not desirable and, hence, there is a need for efficient techniques to enhance the unpredictability.
Clock control of the m-sequence generator is a well-known method that can be used to increase the unpredictability of m-sequence generators.
In most cryptographic applications the outputs of several such clock controlled m-sequence generators are combined to generate the final output sequence. Output bits generated by a combination of clock controlled m-sequence generators form the PN sequence which are used to e.g. encrypt or spread an information signal.
In known applications, e.g. in the ciphering generator A5/1 of the GSM cellular mobile telephone system, the clocking signals for controlling the stepping of the involved clocked m-sequence generators are derived from signals of the clocked m-sequence generators themselves, i.e. the generators are self-clocked.
The A5/1 generator will be described in more detail in connection with FIG. 1, which shows a schematic block diagram of the A5/1 generator.
In the A5/1 generator, three signals (101) are taken from three feedback registers (104) and combined by mapping means (102) in such a way as to derive three clock control signals (103) so that at least two feedback shift registers (104) and sometimes three are always stepped.
There are eight possible values for the combination of input signals (101) which are mapped to the four possible stepping patterns (0,1,1), (1,0,1), (1,1,0), and (1,1,1) (103) if at least two registers are to be stepped. Here (x,y,z) means that if x is 0, the first feedback register is not stepped, and if x is 1, the first feedback register is stepped. In the same way, y and z control the second and third feedback registers, respectively.
Since each feedback shift register (104) is stepped at least three times out of the four possible stepping patterns (102), each shift register (104) is stepped six times out of the eight possible combinations of the input signals (101), since these eight combinations are mapped to the four stepping patterns (103).
Such a uniformity of stepping each shift register (104), responsible for clocking/controlling the connected m-sequence generators (not shown), has an enhancing effect on the unpredictability of the final output PN sequence combined from the output of the m-sequence generators.
However, it is very hard in general to realise such a favourable clocking mechanism with presently known techniques, as e.g. used in A5/1, for other self-clocking methods and/or schemes; especially for methods using a higher number of shift registers (and thereby more m-sequence generators), which is needed e.g. for a higher degree of unpredictability.
Another problem with the prior art as described above is if e.g. four m-sequence generators (and thereby four shift registers) are needed e.g. for a higher degree of unpredictability, and only two shift registers are to be stepped at a time, 16 combinations of input values must be mapped to the 6 possible step patterns (0,0,1,1), (0,1,0,1), (1,0,0,1), (0,1,1,0), (1,0,1,0), (1,1,0,0). With presently known techniques some step patterns will be used more often since the 16 combinations are mapped to only 6 step patterns.
Further U.S. Pat. No. 4,817,145 discloses a generator for generating pseudo random binary cipher sequences comprising a number of subgenerators arranged in a cascaded scheme. A first subgenerator clocks/steps the other subgenerators and is always clocked itself by an external clock at a constant rate.
Even though this prior generator enhances the randomness of the output sequence it is relatively easier to cryptoanalyse since one part of the generator behaves regularly.
An object of the invention is to provide an electrical device for self clocked controlled PN sequence generation where a plurality of PN sequence generators are clocked uniformly with respect to the combinations of input signals.
Another object is to provide flexibility with respect to implementing clock control, so that more freedom with respect to step patterns is possible/available.
This object is achieved by an electrical device of the aforementioned type further comprising:
step pattern generation means adapted to select a step pattern, providing said plurality of clock values (Ct), from a plurality of possible step patterns on the basis of a step pattern select signal (Wt).
Hereby, a final output PN sequence generation will have an enhanced degree of unpredictability since the generation means are clocked uniformly.
Additionally, the uniformity is obtained on the basis of a step pattern select signal (Wt) without using shift registers, which enhances the flexibility of the device, since the step pattern select signal (Wt), responsible for controlling/clocking the sequence generation means, may be obtained by various combinations of different signals instead of mapping means in combination with shift registers.
The enhanced unpredictability and uniformity may be obtained for any number of sequence generation means and any number of stepping patterns.
If the step pattern select signal (Wt) is derived on the basis of a combined value (Ut) and one or more previously derived step pattern select signals (Wtxe2x88x921), a very simple and unpredictable way of deriving the step pattern select signal (Wt) is obtained.
Additionally, the step pattern select signal (Wt) may be provided by using little additional hardware.
In an alternative embodiment, the plurality of sequence generation means (201) is further adapted to output a plurality of step control values (ut), and the combined value (Ut) is provided on the basis of the plurality of step control values (ut) and on the basis of a plurality of prior clock values (Ctxe2x88x921).
Hereby, an efficient and simple use of existing signals is obtained.
A simple way of calculating a step pattern select signal (Wt) is obtained, if the number of the plurality of possible step patterns is 6, and the pattern select signal (Wt) is derived as: Ut+Wtxe2x88x921 MOD 6.
In this way a very simple way of calculating the step pattern select signal (Wt) is obtained by using existing signals, while still obtaining uniformity with respect to the clocking of the sequence generation means.
For another number of possible step patterns than 6 other modulo functions may be applied, e.g. MOD 4 for four possible step patterns.
Alternatively, if the number of the plurality of possible step patterns is 6, and the pattern select signal (Wt) is derived as: Ut+a1 Wtxe2x88x921+a2 Wtxe2x88x922+a3 Wtxe2x88x923 MOD 6, where a1, a2 and a3 are preselected constants, an even better, i.e., resulting in a more unpredictable output PN sequence, way of computing the pattern select signal (Wt) is obtained.
Alternatively, if the number of the plurality of possible step patterns is not a prime number, then the pattern select signal (Wt) is derived on the basis of the combined value (Ut) and the previously derived step pattern select signals (Wtxe2x88x921) using a Chinese remaindering technique.
In this way a very efficient calculation of the pattern select signal (Wt) is obtained, since some calculations of the MOD function may be executed simultaneously.
Another object of the invention is to provide an electrical device comprising a plurality of stepping patterns which reduces power consumption.
This is obtained by choosing the plurality of possible patterns to be: (0,0,1,1), (0,1,0,1), (1,0,0,1), (0,1,1,0), (1,0,1,0), (1,1,0,0).
In this way only two generators are clocked at a time, thereby reducing the power needed.
Additionally, the total power consumption of the total electrical device is independent of the specific stepping pattern used.
In a preferred embodiment, the device further comprises a function generating means (203) adapted to calculate an output value (Outt) as the sum of the plurality of sequence values (zt) MOD 2.
In a preferred embodiment, the plurality of sequence generation means are m-sequence generators.
A further object of the invention is to provide a method of self-clocked controlled PN sequence generation where the PN sequence generators are clocked uniformly with respect to the combinations of input signals.
Another object is to provide flexibility with respect to implementing clock control, so that more freedom with respect to step patterns is possible/available.
This object is achieved by said method of the aforementioned type further comprising the step of:
selecting a step pattern, providing said plurality of clock values (Ct), from a plurality of possible step patterns on the basis of a step pattern select signal (Wt).
Hereby, a final output PN sequence generation will have an enhanced degree of unpredictability since the generation means/generators are clocked uniformly.
Additionally, the uniformity is obtained on the basis of a step pattern select signal (Wt) without using shift registers, which enhances the flexibility of the method, since the step pattern select signal (Wt) may be obtained in many different ways by various combinations of different signals and/or values instead of mapping means in combination with shift registers.
In a preferred embodiment, the step pattern select signal (Wt) is derived on the basis of a combined value (Ut) and one or more previously derived step pattern select signals (Wtxe2x88x921).
Hereby, a very simple way of deriving the step pattern select signal (Wt) is obtained.
Additionally, the step pattern select signal (Wt) may be calculated by using little computational time/complexity.
In yet another embodiment, a plurality of step control values (ut) is output, and said combined value (Ut) is provided on the basis of said plurality of step control values (ut) and on the basis of a plurality of prior clock values (Ctxe2x88x921).
Hereby, an efficient and simple use of existing values is obtained.
In one embodiment, the number of said plurality of possible step patterns is 6, and said pattern select signal (Wt) is derived as: Ut+Wtxe2x88x921 MOD 6.
In another embodiment, the number of said plurality of possible step patterns is 6, and said pattern select signal (Wt) is derived as: Ut+a1 Wtxe2x88x921+a2 Wtxe2x88x922 +a3 Wtxe2x88x923 MOD 6, where a1, a2, and a3 are pre-selected constants.
In yet another embodiment, said pattern select signal (Wt) is derived on the basis of said combined value (Ut) and said previously derived step pattern select signals (Wtxe2x88x921) using a Chinese remaindering technique, if the number of said plurality of possible step patterns is not a prime number.
Another object of the invention is to provide a method comprising a stepping pattern which reduces computational complexity even further.
This is obtained when the plurality of possible step patterns is: (0,0,1,1), (0,1,0,1), (1,0,0,1), (0,1,1,0), (1,0,1,0), (1,1,0,0).
In one embodiment, said method further comprises the step of calculating a value (Outt) as the sum of said plurality of sequence values (Zt) MOD 2.
In another embodiment, said plurality of sequence values (Zt) is generated by a plurality of m-sequence generators, e.g. implemented in software.
The present invention also relates to the use of the method and/or electrical device mentioned above in a portable device. In a preferred embodiment the portable device is a mobile telephone.
Hereby, efficient and more safe encryption of digitized speech or other kind of digital information may be obtained.
Additionally, since only two sequence generation means are clocked at a time, electrical power is saved which is especially important in e.g. a mobile telephone.